
/**
 * 
 * 最小花费爬楼梯
 * 
 * 描述

给定一个整数数组 
c
o
s
t
 
cost  ，其中 
c
o
s
t
[
i
]
 
cost[i]  是从楼梯第
i
 
i 个台阶向上爬需要支付的费用，下标从0开始。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

数据范围：数组长度满足 
1
≤
n
≤
1
0
5
 
1≤n≤10 
5
   ，数组中的值满足 
1
≤
c
o
s
t
i
≤
1
0
4
 
1≤cost 
i
​	
 ≤10 
4
  
 */
public class 最小花费爬楼梯 {
    
    public static void main(String[] args) {
        int[] cost = {1, 100, 1, 1, 1, 100, 1, 1, 100, 1};

        System.out.println(minCostClimbingStairs(cost));
    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param cost int整型一维数组 
     * @return int整型
     */
    public static int minCostClimbingStairs (int[] cost) {
        // write code here
        int n = cost.length;
        int[] dp = new int[n];
        dp[0] = cost[0];
        dp[1] = cost[1];
        for (int i = 2; i < n; i++) {
            dp[i] = Math.min(dp[i - 1], dp[i - 2]) + cost[i];
        }
        return Math.min(dp[n - 1], dp[n - 2]);
    }
}
